﻿#include"sort.h"


pFlight sortFlight(pFlight pos)
{
	pFlight arr[20] = {};
	int k = 0;
	while (pos)
	{
		arr[k++] = pos;
		pos = pos->next;
	}
	//采用希尔排序
	int step = k / 2;
	while (step)//步长为0时结束
	{
		for (int i = step; i < k; i++)//里面的两层循环就是将每一组（间隔相同步长的一组数据）的数据进行插入排序
		{
			pFlight temp = arr[i];
			int j = i - step;
			for (; j >= 0; j -= step)
			{
				if (temp->number < arr[j]->number)
					arr[j + step] = arr[j];
				else
					break;
			}
			arr[j + step] = temp;
		}
		step /= 2;//每次步长减半
	}
	for (int i = 0; i < k - 1; i++)
	{
		arr[i]->next = arr[i + 1];
	}
	if (k >= 1)
		arr[k - 1]->next = NULL;
	return arr[0];
}
void sortLine(Sys sys)
{
	//采用希尔排序
	int step = sys->size / 2;
	while (step)//步长为0时结束
	{
		for (int i = step; i < sys->size; i++)//里面的两层循环就是将每一组（间隔相同步长的一组数据）的数据进行插入排序
		{
			Airline temp = sys->airline[i];
			int j = i - step;
			for (; j >= 0; j -= step)
			{
				if (strcmp(temp.dest, sys->airline[j].dest) > 0)
					sys->airline[j + step] = sys->airline[j];
				else
					break;
			}
			sys->airline[j + step] = temp;
		}
		step /= 2;//每次步长减半
	}
}

BookedList sortBookList(BookedList pos)
{
	if (pos == NULL)return NULL;
	//采用由于数据量较大且杂乱，故采用快速排序
	BookedList arr[300];//采用数组暂时存储
	int i = 0;;
	while (pos)
	{
		arr[i++] = pos;
		pos = pos->next;
	}
	QSort(arr, 0, i - 1);
	for (int j = 0; j < i - 1; j++)
	{
		arr[j]->next = arr[j + 1];
	}
	arr[i - 1]->next = NULL;
	return arr[0];
}


void QSort(BookedList* arr, int s, int t)
{
	if (s < t)
	{
		int div = partition(arr, s, t);
		QSort(arr, s, div - 1);
		QSort(arr, div + 1, t);
	}
}
int partition(BookedList* arr, int low, int high)
{
	int div = low;
	BookedList temp = arr[low];
	while (low < high)
	{
		while (low < high && strcmp(arr[high]->name, temp->name)>0)
		{
			high--;
		}
		arr[low] = arr[high];
		while (low < high && strcmp(arr[low]->name, temp->name) < 0)
		{
			low++;
		}
		arr[high] = arr[low];
	}
	arr[low] = temp;
	return low;
}
